[−][src]Crate elgamal_ristretto

We explain how ElGamal encryption works and how its additive homomorphic property may be exploited. It introduces the zero knowledge proofs currently available in the library.

Table of Contents

These notes explain how the ElGamal encryption works, where we'll cover the following topics:

Notation

We introduce the notation used throughout the documentation.

Let $\mathbb{G}$ denote the Ristretto group with primer order $p$ generated by generator $G$. We write $\mathbb{Z}_p$ to denote the integers modulo $p$. We write $a\leftarrow A$ to denote that $a$ is chosen uniformly at random from the set $A$.

ElGamal Cryptosystem

The ElGamal cryptosystem is defined by three algorithms, \(\texttt{KeyGen}, \texttt{Encrypt} \text{ and }\texttt{Decrypt}\). The key generation algorithm \(\texttt{KeyGen}(G, p)\) outputs a public-private key-pair \(pk = sk \cdot G\) for \(sk \leftarrow\mathbb{Z}_p\). The encryption function \(\texttt{Encrypt}(pk, M)\) takes as input a public key \(pk\) and a message \(M \in G\) and returns a ciphertext \(C = (C_1, C_2) = (r \cdot G, M + r \cdot pk)\) for \(r \leftarrow \mathbb{Z}_p\). The decryption algorithm \(\texttt{Decrypt}(sk, C)\) returns the message \(M = C_2 - sk \cdot C_1\).

Note that the plaintext space is the group \(G\), and hence the plaintexts must be encoded as elliptic curve points. To exploit the additive homomorphic property of ElGamal encryption over the integers modulo $p$, we encode the values as

\[ \texttt{Encode}(x) = x\cdot G \text{ for } x\in \mathbb{Z}_p \]

We make abuse of notation to denote encryption of \(x\in\mathbb{Z}_p\), and write \(\texttt{Encrypt}(x)\) to denote \(\texttt{Encrypt}(\texttt{Encode}(x))\). Using this encoding, we can exploit the additive homomorphic property when encrypting two plaintexts, \(m_1, m_2 \in\mathbb{Z}_p \) as follows:

\[ \begin{aligned} \texttt{Encrypt}(pk, m_1)\oplus\texttt{Encrypt}(pk, m_2) &= (r_1 \cdot G, m_1 \cdot G + r_1 \cdot pk)\oplus (r_1 \cdot G, m_2 \cdot G + r_1 \cdot pk)\\ & = ((r_1 + r_2) \cdot G, (m_1 + m_2) \cdot G + (r_1 + r_2) \cdot pk)\\ & = \texttt{Encrypt}(pk, m_1 + m_2) \end{aligned} \]

Note, however, that when encoding integers using this encoding and exploiting the additive homomorphic property, the decryption procedure requires the discrete logarithm calculation to extract the message:

\[ \texttt{Decrypt}(sk, (r_1 \cdot G, m_1 \cdot G + r_1 \cdot pk)) = m_1 \cdot G \]

Hence, in order to successfully use this encryption scheme as defined above, the plaintext space needs to be small, e.g. the number of votes received by a candidate in an election or wallet balances in a crypto currency.

Important: The current state of the crate does not support encryption/decryption of byte arrays.

Zero Knowledge Proofs

We now introduce notes on the two zero knowledge proofs (ZKP) we decided to include in the crate to offer a higher functionality when using the ElGamal Cryptosystem. These proofs are a proof of correct decryption and a proof of knowledge of a secret key.

We use standard Zero Knowledge Proofs of Knowledge to prove the different operations in the ElGamal cryptosystem and use the zkp compiler to generate them. It uses the Fiat-Shamir heuristic to convert them into non-interactive proofs of knowledge.

The compiler follows the Camenisch-Standler notation to denote proofs and write:

\[ \texttt{ZKP-DL}\lbrace(x), (H), (G): H = (x \cdot G)\rbrace \]

to denote the non-interactive proof of knowledge that the prover knows the discrete logarithm base \(G\) of \(H\), \(x\). We use two different tastes of ZKPs, the aforementioned proof of discrete logarithm, and a proof of equality of discrete log: \[ \texttt{ZKP-DLEQ}\lbrace(x), (A, B, H), (G): H = (x \cdot G) \wedge A = (x \cdot B) \rbrace \]

where the equality of two discrete logs with different bases.

Proof of correct Decryption

Assume that the key-owner of the public key used to encrypt a plaintext, wants to decrypt the ciphertext and proof correctness. Obviously, the interest here is to prove correctness without disclosing any information about the private key itself. For this, we use the following Zero Knowledge Proof.

Recall that the decrypt function performs the following, \(\texttt{Decrypt}(sk, C) = C_2 - sk \cdot C_1 = M\). Moreover, note that \(C = (C_1, C_2) = (r G, M + r Q)\) with \(Q = sk \cdot G\). Then, in order to prove that \(M\) is indeed the correct decryption of \(C\), the prover needs to compute the following proof: \[ \texttt{ZKP-DLEQ}\lbrace(sk), (C_1, (C_2 - M), Q), (G): Q = sk \cdot G \wedge (C_2 - M) = sk \cdot C_1\rbrace \]

Proof of knowledge of secret key

Given a public key, the owner wants to prove that it indeed is the owner of the key. To this end, the owner generates a proof that it knows the discrete log base \(G\) of \(Q\), i.e.: \[ \texttt{ZKP-DL}\lbrace(sk), (Q), (G): Q = sk \cdot G\rbrace \]

Modules

ciphertext
macros
private
public

Macros

define_add_variants